/**
 * https://leetcode-cn.com/problems/same-tree/
 * 判断两棵二叉树, 判断它们是否相同
 * @param p 
 * @param q 
 */
const isSameTree = (p: TreeNode | null, q: TreeNode | null): boolean => {
    // p或者q为空
    if (p === null || q === null) return p === q
    
    if (p.val !== q.val) return false;

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

// 非递归
const isSameTree2 = (p: TreeNode | null, q: TreeNode | null): boolean => {
    // p或者q为空
    if (p === null || q === null) return p === q

    // 使用中序遍历
    const pArr: TreeNode[] = [],
        qArr: TreeNode[] = [];

    let l = p,
        r = q;
    pArr.push(l);
    qArr.push(r)
    while (pArr.length && qArr.length) {
        const n1 = pArr.pop()!
        const n2 = qArr.pop()!

        // 只要又不相同的, 返回false
        if (n1.val !== n2.val) return false

        // 左边的树
        if (n1.left !== null && n2.left !== null) {
            pArr.push(n1.left)
            qArr.push(n2.left)
        } else if ((n1.left === null && n2.left !== null) || (n1.left !== null && n2.left == null)) {
            // 有一边为空, 另一边不为空
            return false
        }


        // 右边的树
        if (n1.right !== null && n2.right !== null) {
            pArr.push(n1.right)
            qArr.push(n2.right)
        } else if ((n1.right === null && n2.right !== null) || (n1.right !== null && n2.right == null)) {
            // 有一边为空, 另一边不为空
            return false
        }
    }

    return true;
};